/**
 * 排序
 *
 * 排序是程序开发中一种非常常见的操作，对一组任意的数据元素（或记录）经过排序操作后，就可以把他们变成一组按关键字排序的有序队列。<br/>
 * 对一个排序算法来说，一般从下面3个方面来衡量算法的优劣：
 * <pre>
 * 1.时间复杂度：它主要是分析关键字的比较次数和记录的移动次数。
 * 2.空间复杂度：分析排序算法中需要多少辅助内存。
 * 3.稳定性：若两个记录A和B的关键字值相等，但是排序后A,B的先后次序保持不变，则称这种排序算法是稳定的；反之，就是不稳定的。
 * </pre>
 * 就现有的排序算法来看，排序大致可分为内部排序和外部排序。<br/>
 * 如果整个排序过程不需要借助外部存储器（如磁盘等），所有排序操作都是在内存中完成，这种排序就被称为内部排序。<br/>
 * 如果参与排序的数据元素非常多，数据量非常大，计算无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘），这种排序就被称为外部排序。<br/>
 * 外部排序最常用算噶是多路归并排序，即将原文件分解称多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序，接下来再对多个有序的子文件进行归并排序。
 * <br/><br/>
 * 就常用的内部排序算法来说，可以分为以下几类：
 * <pre>
 * 选择排序（直接选择排序，堆排序）
 * 交换排序（冒泡排序，快速排序）
 * 插入排序（直接插入排序，折半插入排序，Shell排序）
 * 归并排序
 * 桶式排序
 * 基数排序
 * </pre>
 * <pre>
 * 排 序 法  平均时间           最好时间       最坏时间      额外空间            稳定     备注
 * 冒泡排序  平均O(n^2)         最好O(n)      最坏O(n^2)   辅助空间O(1)         稳定     n较小时好（简单）
 * 选择排序  平均O(n^2)         最好O(n^2)    最坏O(n^2)   辅助空间O(1)         稳定     n较小时好（简单）
 * 插入排序  平均O(n^2)         最好O(n)      最坏O(n^2)   辅助空间O(1)         稳定     基本有序时好（简答）
 * 希尔排序  平均O(nlgn)~O(n^2) 最好O(n^1.3)  最坏O(n^2)   辅助空间O(1)         不稳     n较小时好（简单）
 * 归并排序  平均O(nlgn)        最好O(nlgn)   最坏O(nlgn)  辅助空间O(n)         稳定     n较大时好（较复杂）
 * 快速排序  平均O(nlgn)        最好O(nlgn)   最坏O(n^2)   辅助空间O(lgn)~O(n)  不稳定   n较大时好,基本有序反而不好（较复杂）
 * 堆 排 序  平均O(nlgn)        最好O(nlgn)   最坏O(nlgn)  辅助空间O(1)         不稳定   n较大时好（较复杂）
 * </pre>
 * <p>
 *
 * @author dongfang
 */
package com.df.sort;